#ifndef __CONCURRENTRBTREE_HPP
#define __CONCURRENTRBTREE_HPP

#include "rbtree.h"
#include <utility>
#include <mutex>
#include <condition_variable>
#include <deque>

namespace datastructureZ {
	
	template<typename ElementType> class ConcurrentQueue {
		private:std::deque<ElementType> que;
		private:std::mutex mtx;
		
		public:ConcurrentQueue(void): que() {}
		
		public:void push_back(const ElementType& e) {
			std::lock_guard<std::mutex> lck(mtx);
			
		}
	};
	
	template<typename ElementType> class DataContainerBase {
		
		public:

		virtual bool insert(const ElementType& e) = 0;
		virtual bool remove(const ElementType& _data) = 0;

		virtual const ElementType& nopos(void) = 0;

		DataContainerBase& operator << (const ElementType& e) {
			insert(e);
			return *this;
		}
	};

	template<typename ElementType> class ConcurrentDataContainer:DataContainerBase<ElementType> {

		public:
			
		virtual ElementType& search(const ElementType& _data) = 0;
	};
	
	template<typename ElementType> class ReadOnlyConcurrentDataContainer:DataContainerBase<ElementType> {

		public:
			
		virtual const ElementType& search(const ElementType& _data) = 0;
	};
	
	
	template<typename ElementType> class ConcurrentRBTree: public ReadOnlyConcurrentDataContainer<ElementType> {
		
		public:typedef RBTree<ElementType> Tree;
		
		private:Tree              tree;
		private:const ElementType unuse;
		
		public:ConcurrentRBTree(void (*removeCall)(ElementType& p) = nullptr): tree(removeCall), unuse() {
		}
		
		public:bool insert(const ElementType& e) {
			return false;
		}

		public:bool remove(const ElementType& _data) {
			return false;
		}
		
		public:const ElementType& search(const ElementType& _data) {
			return nopos();
		}
		
		public:const ElementType& nopos(void) {return unuse;}
	};
	
	template<typename ElementType> class ConcurrentRBMapTree: public ConcurrentDataContainer<ElementType> {

		//TODO: work here
		public:typedef RBTree<ElementType> Tree;

		private:Tree         tree;
		private:ElementType  unuse;
		
		private:std::deque<std::pair<char, const ElementType&>> requestQueue; //i:insert, s:search, r:remove
		private:std::mutex rQueueLock;
		
		public:ConcurrentRBMapTree(void (*removeCall)(ElementType& p) = nullptr): tree(removeCall), unuse() {
		}

		public:bool insert(const ElementType& e) {
			return false;
		}
		
		protected:ElementType* _insert(const ElementType& e) {
			return tree._insert(e);
		}

		public:bool remove(const ElementType& _data) {
			return false;
		}

		public:ElementType& nopos(void) {return unuse;}

		public:ElementType& search(const ElementType& _data) {
			return nopos();
		}
	};
	
	template<typename KeyType, typename ValueType> class Map {

		public:
			
		virtual void             put        (const KeyType& k, const ValueType& v) = 0;
		virtual const ValueType& nopos      (void) = 0;
		virtual ValueType&       get        (const KeyType& k) = 0;
		virtual ValueType&       operator [](const KeyType& k) = 0;
		virtual bool             remove     (const KeyType& k) = 0;
	};
	
	template<typename KeyType, typename ValueType> class KVPair {
		public:KeyType   k;
		public:ValueType v;
		
		public:KVPair(const KeyType& _k): k(_k) {}
		public:KVPair(const KeyType& _k, const ValueType& _v): k(_k), v(_v) {}
		
		public:KVPair& operator = (const KVPair& another) { k = another.k; v = another.v; };
		
		public:bool operator >  (const KVPair& another) const { return k > another.k; }
		public:bool operator <  (const KVPair& another) const { return k < another.k; }
		public:bool operator >= (const KVPair& another) const { return k >= another.k; }
		public:bool operator <= (const KVPair& another) const { return k <= another.k; }
		public:bool operator == (const KVPair& another) const { return k == another.k; }
		public:bool operator != (const KVPair& another) const { return k != another.k; }
	};
	
	template<typename KeyType, typename ValueType> class ConcurrentTreeMap: public Map<KeyType, ValueType> {

		public:typedef KVPair<KeyType, ValueType> Pair;
		public:typedef ConcurrentRBMapTree<Pair>  Tree;
		private:Tree      tree;
		private:ValueType unuse;
		
		public:ConcurrentTreeMap(void): tree() {}
		
		public:void put(const KeyType& k, const ValueType& v) {
			tree.insert(Pair(k, v));
		}
		
		public:ValueType& nopos(void) {
			return unuse;
		}
		
		public:ValueType& get(const KeyType& k) {
			Pair& p = tree.search(Pair(k));
			if(p == tree.nopos()) return nopos();
			return p.v;
		}
		
		public:ValueType& operator [](const KeyType& k) {
			Pair& p = tree.search(Pair(k));
			if(p == tree.nopos()) {
				Pair* newPair = tree._insert(newPair);
				return newPair->v;
			}

			return p.v;
		}
		
		public:bool remove(const KeyType& k) {
			return tree.remove(k);
		}
	};
};

#endif
